<?php


/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class BSTIterator {
    private $cur=null;    //定义一个指针 用于指向当前遍历的位置

    function __construct($root) {
        $this->cur=$root;
    }

    function next() {   //Morris遍历实现部分，利用树中空闲的right指针 辅助遍历
        while (1){
            $morrisRight=$this->cur->left;
            if($morrisRight!=null){
                while ($morrisRight->right!=null && $morrisRight->right!=$this->cur) $morrisRight=$morrisRight->right;
                if($morrisRight->right==null){      //找到左子树的最右节点，并将其指向上一层节点
                    $morrisRight->right=$this->cur;
                    $this->cur=$this->cur->left;
                    continue;
                }
            }
            break;
        }
        $v=$this->cur->val;               //输出当前值，并将指针右移
        $this->cur=$this->cur->right;
        return $v;
    }

    function hasNext() {
        return $this->cur!=null;   //当前指针为空，整颗树遍历完毕
    }
}





?>